//
// This file is part of cpp-lib, a library of C++ functions and classes.
// Cpp-lib is copyright (C) 2004 and onwards, The CPL Interest Group.
// 
// This library is free software; you can redistribute it and/or modify it
// under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation; either version 2.1 of the License, or (at
// your option) any later version.
// 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser
// General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with this library (see the file COPYING); if not, write to the
// Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
// 02111-1307  USA
//
// $Id$
//


#include <cmath>
#include <algorithm>
#include <vector>

#include "cpp-lib/math-util.h"

using namespace cpl::math ;



int cpl::math::log_2( const long x ) {

  assert( x > 0 ) ;

  long p = 1 , log = 0 ;

  while( 2 * p <= x ) { p *= 2 ; ++log ; }

  assert( 1 << log == p ) ;
  assert( p <= x ) ;
  assert( x < 2 * p ) ;

  return log ;

}


long cpl::math::next_power_of_two( const long x ) {

  if( x == 0 ) return 1 ;

  assert( x > 0 ) ;

  long y = 1 << cpl::math::log_2( x ) ;

  if( y < x ) y *= 2 ;
  assert( x <= y ) ;
  assert( y < 2 * x ) ;

  return y ;

}


long cpl::math::bit_reversal( const long x , const int l ) {

  assert( l >= 1 ) ;
  assert( 0 <= x ) ;
  assert( x < ( 1 << l ) ) ;

  long mask_x = 1 ,
       mask_y = 1 << ( l - 1 ) ;

  long y = 0 ;

  do {

    if( x & mask_x ) y |= mask_y ;
    mask_x <<= 1 ;
    mask_y >>= 1 ;

  } while( mask_y ) ;

  assert( 0 <= y ) ;
  assert( y < ( 1 << l ) ) ;

  return y ;

}
